#说明： 将k进制的数字x转换为10进制
#输入：k:int,  x:str
#otput: int
import sys
from logging import fatal

int_to_char = "0123456789ABCDEF"
char_to_int = {}
for idx, chr in enumerate(int_to_char):
    char_to_int[chr] = idx
# print(char_to_int)

def k_to_ten(k, x):
    ans = 0
    for i in range(len(x)):
        ans = ans * k + char_to_int[x[i]]
    return ans

# k = 5
# x = '1101'
# print(k_to_ten(k,x))


#from 10 to k
def ten_to_k(num, k):
    ans = ""
    while num:
        ans += int_to_char[num % k]
        num //= k
    return ans[::-1]

# num = 18
# k = 2
# print(ten_to_k(num, k))

#任意的进制转换
def s_to_m(n, m, x):
    ans = 0
    for i in range(len(x)):
        ans = ans * n + char_to_int[x[i]]
    res = ""
    while ans:
        res += int_to_char[ans % m]
        ans //= m
    return res[::-1]

T = int(input())
for i in range(T):
    n ,m = map(int, input().split())
    print(n, m)
    x = sys.stdin.readline().strip()
    print(s_to_m(n, m, x))